/**
 * Description: 位图
 *
 * @author weiruibai.vendor
 * Date: 2022/7/21 10:40
 */
public class BitMap {

    public static void main(String[] args) {

        int[] arr = new int[]{1, 4, 5, 7};
        BitMap bitMap = new BitMap(7);
        bitMap.add(1);
        bitMap.add(2);
        bitMap.add(3);
        bitMap.add(4);
        System.out.println(bitMap.isContains(3));
        bitMap.delete(3);
        System.out.println(bitMap.isContains(3));
        bitMap.add(5);
        bitMap.add(6);
        System.out.println(bitMap.isContains(7));
        bitMap.add(7);
        System.out.println(bitMap.isContains(7));
        bitMap.delete(7);
        System.out.println(bitMap.isContains(7));
        bitMap.add(8);
        System.out.println("====");
    }

    long arr[];

    public BitMap(int max) {
        arr = new long[(max + 64) >> 6];
    }

    public void add(int num) {
        // num应该放在位图中哪个位置
        int position = getPosition(num);
        arr[position] |= (1l << (num % 64));
    }

    public void delete(int num) {
        if (isContains(num)) {
            int position = getPosition(num);
            arr[position] = arr[position] & (1 << position);
        }
    }

    public boolean isContains(int num) {
        int position = getPosition(num);
        return (arr[position] & (1l << (num % 64))) != 0;
    }

    private int getPosition(int num) {
        // 等价于 num / 64
        return num >> 6;
    }
}
